package com.hardy.leetcode;

import java.util.Set;

/**
 * User: Ruijie Date: 2016/8/1
 */
public class WordBreak {
    public static boolean wordBreak(String s,Set<String> dict){
        int len=s.length();
        boolean[] result=new boolean[len+1];
        result[0]=true;
        for(int i=0;i<len;i++){
            if(!result[i]){
                continue;
            }
            for(String str:dict){
                int l=str.length();
                int end=i+l;
                if(end>s.length()){
                    continue;
                }
                if(result[end]){
                    continue;
                }
                if(s.substring(i,end).equals(str)){
                    result[end]=true;
                }
            }
        }
        return result[s.length()];
    }
    public boolean wordBreak1(String s, Set<String> dict) {
        return help(s,dict,0);
    }
    public static boolean help(String s,Set<String> dict,int start){
        if(start==s.length()){
            return true;
        }
        for(String str:dict){
            int len=str.length();
            if(s.substring(start,start+len).equals(str)){
                if(help(s,dict,start+len)){
                    return true;
                }
            }
        }
        return false;
    }
    public static void main(String[] args) {

    }
}
